Common processor systems utilize the concept of address translation in a processor pipeline to change the address of a page of data or instructions from its virtual storage address to its real, physical storage address. One means of address translation utilizes a translation lookaside buffer (TLB) which conventionally stores many entries where each entry includes an application space identifier (ASID) also referred to as a process identifier (PID), a virtual address tag (VT), and a physical page number (PPN). Thus, the translation lookaside buffer contains the mapping between a virtual address with a physical address. In its simplest form, the processor pipeline receives as input a virtual address of an instruction, compares a portion of the virtual address with the entries in the TLB to find a matched entry, and replaces the portion of the virtual address with the physical page number associated with the matched entry to form a physical address. A given mapping of a physical address to a virtual address generally covers a range of the virtual and physical address space, this range being referred to as a “page”, with the size of a page generally being greater than the size of a cache line in an instruction cache, such that several cache lines may all be associated with the same page of the virtual or physical address space.
Common processor systems also include one or more instruction caches which store recently used instructions in fast on-chip memory to minimize the delay resulting from fetching instructions from slower off-chip memory. An instruction cache may be indexed to efficiently look up an entry. The term “indexed” as used in relation to instruction caches means a set of bits in either a virtual address or physical address which are utilized to specify a set in a set-associative instruction cache or a row in a directly mapped instruction cache. An instruction cache indexed by bits within a virtual address is known as a virtually indexed cache. An instruction cache indexed by bits within a physical address is known as a physically indexed cache.
Entries in an instruction cache may be tagged with a key which is compared with either a portion of a physical address or a portion of a virtual address. An instruction cache tagged with a portion of a physical address is known as a physically tagged instruction cache. An instruction cache tagged with a portion of a virtual address is known as a virtually tagged instruction cache. A processor designer chooses how an instruction cache is both indexed and tagged. Conventional instruction caches may be either virtually indexed virtually tagged (VIVT), virtually indexed physically tagged (VIPT), or physically indexed physically tagged (PIPT). Through address translation, a virtual address is converted to a physical address which may be utilized to look up an entry in a physically tagged instruction cache or to access real memory in the case of an instruction cache miss.
In addition to a virtual address tag, conventional virtually tagged instruction caches commonly include an ASID or a PID tag. This tag allows the processor system to discriminate whether an address entry is valid for the active software process. For example, if the processor system is executing instructions associated with a software process having ASID ‘x’, a successful cache match would require matching both the ASID tag and the virtual address instruction tag. Because of various scenarios such as swapping of an active ASID, that is, replacing one process using a given ASID value with a new process using that same ASID value, virtually tagged instruction caches may have one or more entries that become obsolete and are no longer valid. Since cache hits save processors time from fetching instructions from memory, processor system designers desire cache coherency, a cache whose contents reflect valid, non-obsolete instructions. To maintain cache coherency, entries in a cache are commonly invalidated in response to common instruction cache invalidate instructions issued by a software application. The amount of management of an instruction cache required by the software application is dependent on whether the instruction cache is virtually tagged or physically tagged. Since one or more virtual addresses may map to a given physical address, alias and synonym problems may exist in a conventional virtually tagged instruction cache.
The alias problem occurs when two or more I-cache entries containing different virtual address/ASID combinations map to the same physical address. These different combinations may occur due to any of the following three reasons. First, the virtual address of two or more I-cache entries may be literally different but part of the same software process having the same ASID field value. Second, the virtual addresses of two or more I-cache entries may be the same but associated with different software processes and, thus, associated with different ASID field values. Third, the virtual addresses of two or more I-cache entries may all be different and associated with different software processes, thus, associated with different the ASID values. In any of these three cases, the different combinations can map to the same physical address. As a result of this alias problem, conventional virtually tagged instruction caches impose a burden on a software application to issue I-cache invalidate instructions for more scenarios than required by a physically tagged instruction cache. For example, a software application written to virtually tagged instruction caches would have to issue instruction cache invalidate instructions to invalidate each virtual address in the instruction cache that may be associated with a physical address that has itself become invalid or been modified.
The synonym problem refers to two or more I-cache entries that are located at different virtual indices of the I-cache, but which are associated with the same physical address. The synonym problem may occur in conventional virtually-indexed I-caches regardless of whether those I-caches are virtually or physically tagged.
Virtually-tagged instruction caches also impose another additional burden on software for invalidating I-cache entries, relative to physically-tagged instruction caches. Specifically, when the mapping for the combination of a given ASID and page of the virtual address space is changed from one physical address to another, all of the I-cache entries in a virtually-tagged I-cache that are associated with that combination of ASID and page of the virtual address space are no longer valid, since the I-cache may have cached the contents of the old physical memory locations associated with the old mapping, rather than the contents of the new physical memory locations associated with the new mapping. This is true even though the actual contents of the underlying old and new physical memory locations may not have changed. Therefore, software written to manage a virtually-tagged instruction cache must execute instruction cache invalidate operations to invalidate all instruction cache entries that might be associated with the combination of ASID and page of the virtual address space for which the mapping was changed.
In a processor with a virtually tagged instruction cache, address translation may be performed in a pipeline in parallel with looking up instructions from the virtually tagged instruction cache. Thus, this parallelism provides advantageous power, frequency, and instruction throughput when virtually tagged instruction caches are utilized. Therefore, there is a need for an instruction cache system and methods which achieve the advantages of a conventional virtually tagged instruction cache while eliminating the additional burden placed on software applications by conventional virtually tagged instruction caches with regard to managing entries and do not impose added requirements to software applications.